package problem;

import java.util.*;

public class S_107 {
    //二叉树的自底向上的层次遍历
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    //迭代
    class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> res=new ArrayList<>();
            if(root==null) return res;
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                List<Integer> tmp=new ArrayList<>();
                for(int i=0;i<size;i++){
                    TreeNode node=queue.poll();
                    tmp.add(node.val);
                    if(node.left!=null) queue.offer(node.left);
                    if(node.right!=null) queue.offer(node.right);
                }
                res.add(tmp);
            }
            Collections.reverse(res);
            return res;
        }
    }
    //递归
    class Solution1{
          public List<List<Integer>> levelOrderBottom(TreeNode root){
              List<List<Integer>> res=new ArrayList<>();
              helper(res,root,0);
              return res;
          }
          private void helper(List<List<Integer>> res,TreeNode root,int depth){
              if(root==null) return;
              if(res.size()==depth) res.add(new ArrayList<>());
              res.get(res.size()-depth-1).add(root.val);
              if(root.left!=null) helper(res,root.left,depth+1);
              if(root.right!=null) helper(res,root.right,depth+1);
          }
    }
}
